A tree structure (or simply a “tree”) is an acyclic connected graph of nodes where each node has zero or more child nodes and at most one parent node. The top-level node of a tree is called the root node. Each node of the tree may be associated with a data set. A tree may be used to illustrate the hierarchical relationships between the data sets associated with the nodes of the tree. As a result, data that represents a tree structure, or a portion thereof, or is otherwise arranged in a hierarchical manner is referred to herein as hierarchical data.
Trees may be useful in many contexts involving hierarchical data. For example, XML is a popular specification for structuring data that is widely used by many applications. An XML document, which is a set of data that conforms to the XML specification, is arranged as a tree structure. Thus, any application that manipulates an XML document or displays an XML document to a user interacts with nodes of a tree.
Many applications visually depict hierarchical data to a user by displaying the hierarchical data as a tree. As some trees may comprise a large number of nodes, many user interfaces allow a user to perform a paging operation or a scrolling operation on a displayed portion of the tree to display a different portion of the tree. For example, some trees may comprise thousands to hundreds of thousands of nodes, and therefore, it may not be possible for all the nodes of the tree to be simultaneously depicted on a screen at once. By enabling a user to page or scroll the tree being displayed to the user, the user may view portions of the tree that are not currently displayed to the user.
A problem with performing paging or scrolling operations on a tree is that the operations require a large amount of memory. Currently, when a user issues a request to an application to perform a paging operation on a tree, the application must traverse (or “walk”) the tree in order to determine which nodes of the tree should be displayed to the user on the requested page. To illustrate, if a user issues a request to perform a paging operation to update the portion of the tree that is displayed to the next page, then the application must identify those nodes of the tree which are on the next page. The application does this by walking the tree to examine each node to determine if it should be displayed on the requested page. For example, the application may identify all the child nodes of the root nodes, determine whether those child nodes are displayed on the requested page, then identify all the child nodes of nodes of the second level of the tree to determine whether those nodes are displayed on the requested page, and so on, until all the nodes of the tree which are on the requested page are identified.
Consequently, to walk a tree comprising a large number of nodes, a large amount of memory and computational resources are required, as each node of the tree that is examined, or “walked,” is typically loaded into memory. Indeed, the larger the tree, the more memory and computational resources are required to perform a paging operation. This is undesirable, as an increase in the consumption of memory and computational resources of a computerized system tends to decrease performance of the computerized system. Browsing large trees (such as a tree having more than 5000 nodes) should be perceived as being fast and time and computational resources required to browse the tree should be independent of the number of nodes in the tree; however, no approach for doing so is currently known in the art.